//最小基因变化
class Solution {

public:
    char d[5] = "ACGT";
    unordered_set<string> vis;
    int minMutation(string startGene, string endGene, vector<string>& bank) {
        int ret = 0;
        unordered_set<string> b_hash(bank.begin(), bank.end());
        queue<string> q;
        q.push(startGene);
        vis.insert(startGene);
        while (q.size()) {
            int sz = q.size();
            //  string t = q.front();
            //cout << t << ' ';
            ret++;
            // return ret;
            // q.pop();
            for (int i = 0; i < sz; i++) {
                string t = q.front();
                q.pop();
                string temp = t;
                for (auto& c : temp) {
                    temp = t;
                    for (int j = 0; j < 4; j++) {
                        c = d[j];
                        if (b_hash.count(temp) && !vis.count(temp)) {
                            if (temp == endGene)
                                return ret;
                            q.push(temp);
                            vis.insert(temp);
                        }
                        // cout << temp << " ";
                    }
                    // cout << endl;
                }
            }
        }
        return -1;
    }
};

//单词接龙
class Solution {
public:
    int ladderLength(string beginWord, string endWord,
                     vector<string>& wordList) {
        unordered_set<string> hash(wordList.begin(), wordList.end());
        unordered_set<string> vis;
        queue<string> q;
        vis.insert(beginWord);
        q.push(beginWord);
        int ret = 0;
        while (q.size()) {
            int sz = q.size();
            ret++;
            for (int i = 0; i < sz; i++) {
                string t = q.front();
                q.pop();
                string temp = t;
                for (auto& c : temp) {
                    temp = t;
                    for (char j = 'a'; j <= 'z'; j++) {
                        c = j;
                        if (!vis.count(temp) && hash.count(temp)) {
                            if (temp == endWord)
                                return ret + 1;
                            q.push(temp);
                            vis.insert(temp);
                        }
                    }
                }
            }
        }
        return 0;
    }
};